package main

import "fmt"

func main() {
	var node1, node2, node3, node4, node5 *TreeNode
	node5 = &TreeNode{7, nil, nil}
	node4 = &TreeNode{15, nil, nil}
	node3 = &TreeNode{20, node4, node5}
	node2 = &TreeNode{9, nil, nil}
	node1 = &TreeNode{3, node2, node3}

	printTree(node1)

	fmt.Println(maxDepth(node1))

}

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func maxDepth(root *TreeNode) int {
	if root == nil {
		return 0
	}
	// 向下递归压栈，不做计算操作，每层+1为栈深计数
	return max(maxDepth(root.Left), maxDepth(root.Right)) + 1
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

// 链表遍历与递归差不多，树递归要比循环轻松多
func maxDepth1(root *TreeNode) int {
	var check func(root *TreeNode, de int) int
	check = func(root *TreeNode, de int) int {
		if root == nil { // 递归返回条件
			return de // 递归弹栈的开始，一路将这个值作为返回值弹出去和其他子树的结果做比较
		}

		leftDeep := check(root.Left, de+1)   // 左子树递归压栈
		rightDeep := check(root.Right, de+1) // 右子树递归压栈
		if leftDeep > rightDeep {
			return leftDeep
		}
		return rightDeep
	}

	return check(root, 0)
}

func printTree(root *TreeNode) {
	if root == nil {
		fmt.Printf("%+v \t", nil)
		return
	}
	fmt.Printf("%d \t", root.Val)
	printTree(root.Left)
	printTree(root.Right)
}
